Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs

摘要

Ryser's Conjecture states that for any $r$-partite $r$-uniform hypergraph thevertex cover number is at most $r-1$ times the matching number. This conjectureis only known to be true for $r\leq 3$. For intersecting hypergraphs, Ryser'sConjecture reduces to saying that the edges of every $r$-partite intersectinghypergraph can be covered by $r-1$ vertices. This special case of theconjecture has only been proven for $r \leq 5$. It is interesting to study hypergraphs which are extremal in Ryser'sConjecture i.e, those hypergraphs for which the vertex cover number is exactly$r-1$ times the matching number. There are very few known constructions of suchgraphs. For large $r$ the only known constructions come from projective planesand exist only when $r-1$ is a prime power. Mansour, Song and Yuster studiedhow few edges a hypergraph which is extremal for Ryser's Conjecture can have.They defined $f(r)$ as the minimum integer so that there exist an $r$-partiteintersecting hypergraph $\mathcal{H}$ with $\tau({\mathcal{H}}) = r -1$ andwith $f(r)$ edges. They showed that $f(3) = 3, f(4) = 6$, $f(5) = 9$, and$12\leq f(6)\leq 15$. In this paper we focus on the cases when $r=6$ and 7. We show that $f(6)=13$improving previous bounds. We also show that $f(7)\leq 22$, giving the firstknown extremal hypergraphs for the $r=7$ case of Ryser's Conjecture. Theseresults have been obtained independently by Aharoni, Barat, and Wanless.